package com.shr.code_interview;

import java.util.ArrayList;

public class Solution_34 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        int currentSum = 0;
        findPath(root, currentSum, target, path, paths) ;
        return paths ;
    }

	private void findPath(TreeNode root, int currentSum, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
		if(root == null)
			return ;
		path.add(root.val) ;
		currentSum += root.val ;
		if(root.left == null && root.right==null && currentSum == target){
			ArrayList<Integer> newList = new ArrayList<>(path.size());
			newList.addAll(path) ;
			paths.add(newList) ;
		}
		
		if(root.left != null)
			findPath(root.left, currentSum, target, path, paths);
		if(root.right != null)
			findPath(root.right, currentSum, target, path, paths);
		
		path.remove(path.size()-1) ;
			
	}
}
